const MAX = Number.MAX_SAFE_INTEGER

function divide(p, r) {
  return Math.floor((p + r) / 2)
}

function conquer(arr, p, q, r) {
  let arr1 = arr.slice(p, q)
  let arr2 = arr.slice(q, r)
  arr1.push(MAX)
  arr2.push(MAX)
  for (let k = p, i = 0, j = 0; k < r; k++) {
    arr[k] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++]
  }
}
// 归并排序 时间复杂度O(nlgn)+O(n)
function mergeSort(arr, p = 0, r) {
  r = r || arr.length
  if (r - p === 1) return
  if (r - p === 2) {
    if (arr[p] > arr[r-1]) {
      [arr[p], arr[r - 1]] = [arr[r - 1], arr[p]]
    }
    return;
  }

  const q = divide(p, r)
  mergeSort(arr, p, q)
  mergeSort(arr, q, r)
  conquer(arr, p, q, r)
}

let a = [1, 2, 4, 3]
mergeSort(a)
console.log(a)